#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include"xh.h"
searchTree MakeEmpty(searchTree T) {
	if (T != NULL) {
		MakeEmpty(T->left);
		MakeEmpty(T->right);
		free(T);
	}
	return NULL;
}

position Find(searchTree T, ElementType x) {
	if (T == NULL)
		return NULL;
	else if (x < T->element) {
		return Find(T->left, x);
	}
	else if (x > T->element) {
		return Find(T->right, x);
	}
	else
		return T;
}

position Findmin(searchTree T) {
	if (T == NULL) {
		return NULL;
	}
	else if (T->left == NULL) {
		return T;
	}
	else
		return Findmin(T->left);
}

position Findmax(searchTree T) {
	if (T == NULL) {
		return NULL;
	}
	else if (T->right == NULL) {
		return T;
	}
	else
		return Findmin(T->right);
}

searchTree Insert(searchTree T,ElementType x) {
	if (T == NULL) {
	    T =(position)malloc(sizeof(struct SearchTree));
		if (T == NULL) {
			perror("malloc");
			return NULL;
		}
		else{
			T->element = x;
			T->left = T->right = NULL;
		}
	}
	else if (x < T->element) {
		T->left = Insert(T->left, x);
	}
	else if(x>T->element){
		T->right = Insert(T->right, x);
	}
	return T;
}

ElementType NowNode(position T) {
	return T->element;
}


searchTree Delete(searchTree T,ElementType x) {
	if (T == NULL) {
		printf("Tree is null, delete fail\n");
		return NULL;
	}

	if (x < T->element)
		T->left = Delete(T->left,x);
	else if (x > T->element)
		T->right = Delete(T->right,x);
	else {
		searchTree TmpCell;
		if (T->left && T->right) {
			TmpCell = Findmin(T->right);
			T->element = TmpCell->element;
			T->right = Delete(T->right, T->element);
		}
		else {
			TmpCell = T;
			if (T->left == NULL)
				T = T->right;
			else if (T->right == NULL)
				T = T->left;
			free(TmpCell);
		}
	}
	return T;
}

void inorderTree(searchTree T) {
	if (T!= NULL) {
		//return;//printf("Tree is Empty!");error

		inorderTree(T->left);
		printf("%d ", T->element);
		inorderTree(T->right);
	}
}